package org.example.sword2offer.primary;



/**
 * @author: lynn
 * @Descript:
 * @date: 2021/3/8 20:23
 *
 * Question 15
 * p1 {1,2,3,4,5}
 * p2 {1,2,3,4,5}
 *
 * p1-2 --> {3,4,5}
 * p2 跟p1 等长为空
 * p2 --> {4,5},2  --> {4,5}
 * @version: 1.0
 */
public class Q15_FindKthToTail {

    public static void main(String[] args) {
        ListNode  node=new ListNode(3);
        node.next=new ListNode(6);
        node.next.next=new ListNode(9);
        node.next.next.next=new ListNode(11);
        node.next.next.next.next=new ListNode(13);
        node.next.next.next.next.next=new ListNode(14);
        System.out.println("第k个节点: "+FindKthToTail(node,3));
    }

    public static ListNode FindKthToTail (ListNode head, int k) {
        if(head == null || k <= 0){
            return null;
        }
        //定义一个临时节点指向head，让它给p1.p2赋值，
        ListNode tmp = new ListNode(0);
        tmp.next = head;


        ListNode p1 = tmp, p2 = tmp;
        while(k > 0 && p1.next != null){
            p1 = p1.next;
            k--;
        }
        //length < k
        if(k != 0){
            return null;
        }
        while(p1 != null){
            p1 = p1.next;
            p2 = p2.next;
        }
        tmp = null; //help gc
        return p2;
    }

    private static ListNode doRever(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode preNode = null;//前一个节点指针
        ListNode curNode = head;//当前节点指针
        while (curNode!=null){
            ListNode nextNode= curNode.next;
            curNode.next=preNode;
            preNode=curNode; //3
            curNode=nextNode; //  第三步和第四部不能乱
        }
        return preNode;
    }

    private static class ListNode {
        int val;  //这个是值
        ListNode next = null; //指针
        public ListNode(int val) {
            this.val = val;
        }
    }
}
